package com.kingwood.algorithm.test;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringJoiner;

/**
 * 数学相关的运算
 */
public class ShuXue {

    /**
     * 素数之积
     * https://fcqian.blog.csdn.net/article/details/125985026
     * 给定一个 32 位正整数，请对其进行因数分解，找出是哪两个素数的乘积。
     * @param n
     * @return
     */
    public static String getSuShuZhiJi(int n) {
        if(isPrime(n)) {
            return "-1 -1";
        }

        // 假设i为n的因子
        for (int i=2; i<n; i++) {
            // 若n不能整除i,则i不是n的因子，继续下次循环，找新的i
            // 若n可以整除i,则i就是n的因子
            if(n % i == 0) {
                // j为n的另一因子
                int j = n / i;
                // 只有i,j因子都为素数时，n才是符合题意的素数之积
                if (isPrime(i) && isPrime(j)) {
                    // 如果n为两个素数之积，则n只能分解为这两个因子，因为素数无法再次分解出其他因子，也就是说n不再有其他因子了（因子不包含1和自身）
                    return i < j ? i + " " + j : j + " " + i;
                } else {
                    // 如果i，j有一个不是素数因子，则说明n存在非素数因子，此时n不可能是素数之积
                    // 如果i，j为相同的素数因子，则n不是满足题意的素数之积
                    // 此时可以判定n不符合要求了，直接退出循环
                    break;
                }
            }
        }

        return "-1 -1";
    }

    public static String getSuShuZhiJi1(int n) {
        if (isPrime11(n)) {
            return "-1 -1";
        }

        // 假设i为n的因子
        for (int i=2; i<n; i++) {
            if (n % i == 0) {
                int j = n / i;
                if (isPrime11(i) && isPrime11(j)) {
                    return i < j ? i + " " + j : j + " " + i;
                } else {
                    break;
                }
            }
        }

        return "-1 -1";
    }

    /**
     * 判定一个数是不是素数
     * 素数又叫质数，素数是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。
     * @param n
     * @return
     */
    public static boolean isPrime1(int n) {
        if (n <= 3) {
            return n > 1;
        }
        if (n % 2 == 0) {
            return false;
        }

        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

    public static boolean isPrime11(int n) {
        if (n <= 3) {
            return n > 1;
        }

        if (n %2 == 0) {
            return false;
        }

        double len = Math.sqrt(n);
        for (int i=3; i<=len; i+=2) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

    /**
     * 判定一个数是不是素数
     * 素数又叫质数，素数是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。
     * @param n
     * @return
     */
    public static boolean isPrime(int n) {
        if (n <= 3) {
            return n > 1;
        }

        int yu6 = n % 6;
        if (yu6 != 1 && yu6 != 5) {
            return false;
        }

        double nSqrt = Math.sqrt(n);
        for (int i=5; i<=nSqrt; i+=6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }

        return true;
    }

    /**
     * 用连续自然数之和来表达整数
     * https://fcqian.blog.csdn.net/article/details/127341945
     * @param t
     */
    public static void jigeLianxuZiranshuSum(int t) {
        int[] arr = new int[t];
        for (int i = 0; i < t; i++) {
            arr[i] = i + 1;
        }

        ArrayList<int[]> ans = new ArrayList<>();

        int l = 0;
        int r = 1;

        int sum = arr[l];
        while (l < t) {
            if (sum > t) {
                sum -= arr[l++];
            } else if (sum == t) {
                ans.add(Arrays.copyOfRange(arr, l, r));
                sum -= arr[l++];
                if (r >= t) break;
                sum += arr[r++];
            } else {
                sum += arr[r++];
            }
        }

        ans.sort((a, b) -> a.length - b.length);

        for (int[] an : ans) {
            StringJoiner sj = new StringJoiner("+");
            for (int v : an) {
                sj.add(v + "");
            }
            System.out.println(t + "=" + sj);
        }

        System.out.println("Result:" + ans.size());
    }

    public static void main(String[] args) {
        jigeLianxuZiranshuSum(20);
    }
}
